package 动态规划.区间DP;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Scanner;
import java.io.IOException;
/**
 * 还有一个  进阶的 版本 数据  量 非常的 大 
 * 困难 程度 
 * 应该是 
 * 
 */
/**
 * 至于 这个 过程 是什么 个 情况 希望通过这个 题 能让你 明白一些
 *   区间dp 问题 
 * Acwing  记忆化 搜索 超时 了
 * 换成   out.write();
 * out.flush();
 * 照样超时 卧槽 
 * 就不是 想让你 用 记忆化 搜索  ac的
 *
 * 在一个操场上一排地摆放着N堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，
 * 并将新的一堆石子数记为该次合并的得分。请设计一个程序，
 * 计算出将N堆石子合并成一堆的最小得分
 *
 *
 * @author I adore you
 *
 */
public class Acwing282石子合并 {
	static int preSum []  = new int [310] ;
	static int nums[] = new int [310];
	static int INF  = Integer.MAX_VALUE;
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
	static Scanner sc = new Scanner(System.in);
	public static void main(String []args) throws IOException{
		/**
		 * 这里   还是  输入输出 问题 
		 *  就直接 全部 使用  in.readLine();
		 *  来读入 所有的数据  就不会出现 这样的 问题
		 * 
		 */
		int N = sc.nextInt();
//		int c = in.read();
//		System.out.println(c);
//		System.out.print((char)(c) + " he");
		String line [] = in.readLine().split(" ");
		for(int i = 1;i <= N;i++) {
			nums[i] = Integer.parseInt(line[i - 1]);
			preSum[i] = preSum[i - 1] + nums[i];
		}
//		for(int  i : preSum)
//			System.out.print(i + " ");
//		System.out.println(N);
		for(int arr [] : record)
		Arrays.fill(arr, -1);
		System.out.println(memorySearch(1,N));
		System.out.println(solution(1,N));
		System.out.println(dp(1,N));
	}
	static int solution(int i,int j) {
		if(i == j)
			return 0;
		int ans  = INF;
		for(int  k = i;k < j ;k++) {
			ans = Math.min(ans, solution(i,k) + solution(k + 1,j) + preSum[j] - preSum[i - 1]);
		}
		return ans ;
	}
	static int record [][] = new int [310][310];
	static int memorySearch(int i,int j) {
		/**
		 * 为啥 使用 记忆化 搜索 
		 * 因为 有 大量的 重复的 子过程 
		 * 
		 * 如果  缓存表 中 有记录 那就直接 返回 之前 记录的 值
		 */
		if(record[i][j] != -1)
			return record[i][j];
		if(i == j)
			return record[i][j] = 0;
		
		int ans = INF;
		/**
		 * 之前 都是 求 最多 最大的 情况 现在 是 求最小的 情况
		 * 所以  这里的 ans  值的 赋值  要根据  题意 
		 * 要不然 纠错 很烦  的
		 */
		/**
		 * 为啥 k 不直接 从 i + 1  直接 开始 计算 而是 从 i 开始
		 * 可能 考虑 到 i， j 是 相邻的 两个 值的 话
		 * 这里 还得 去 多多 思考一下 这些 
		 */
		for(int k = i;k < j;k++) {
			ans = Math.min(ans, memorySearch(i,k) + memorySearch(k + 1,j) + preSum[j] - preSum[i - 1]);
		}
		return ans;
	}
	static int dp [][] = new int [310][310];
	static int dp(int begin,int end) {
		
		for(int i = end ;i >= 1;i--) {
			for(int j = 1;j <= end ;j++ ) {
				/**
				 * 一定要 把 所有的 basecase 的条件在这里
				 * 在 dp  数组中进行 一个 赋值 
				 * 这是  暴力 递归 到 dp 中 的 一个 很重要的 点  
				 */ 
				if(i == j)
					continue;
				int ans = Integer.MAX_VALUE;
				for(int k = i ;k < j;k++) {
					ans = Math.min(ans, dp[i][k] + dp[k + 1][j] + preSum[j] - preSum[i - 1]);
				}
				dp[i][j] = ans;
			}
		}
		return dp[begin][end];
	}
}
